Deutsche Edition 1/Deutsche Edition 1.iso/amok/amok_lha/amok70.lha/PL0/txt/GeneralParser.mod

Text File | 1993-08-15 | 5KB | 233 lines

MODULE GeneralParser;

IMPORT
  io,
  asc: ASCII,
  fs: FileSystem,
  sys: SYSTEM;

TYPE
  NodePtr = POINTER TO Node;
  HeadPtr = POINTER TO Header;

  Node = RECORD
    suc, alt: NodePtr;
    terminal: BOOLEAN;
    tsym: CHAR;
    nsym: HeadPtr;
  END;

  Header = RECORD
    sym: CHAR;
    entry: NodePtr;
    suc: HeadPtr;
  END;

CONST
  empty = " ";

VAR
  list, sentinel, h: HeadPtr;
  q, r, s: NodePtr;
  sym: CHAR;
  noerr: BOOLEAN;
  file: fs.File;


PROCEDURE GetSym;
BEGIN
  REPEAT
    IF fs.ReadChar(file,sym) THEN END;
    io.Write(sym);
  UNTIL (sym > " ") OR (sym = asc.esc);
END GetSym;


PROCEDURE find(s: CHAR; VAR h: HeadPtr);
VAR
  h1: HeadPtr;
BEGIN
  h1 := list;
  sentinel.sym := s;
  WHILE h1.sym # s DO
    h1 := h1.suc; END;
  IF h1 = sentinel THEN (* insert *)
    NEW(sentinel);
    h1.suc := sentinel;
    h1.entry  := NIL;
  END;
  h := h1;
END find;


PROCEDURE error;
BEGIN
  noerr := FALSE;
  io.WriteString("\n incorrect Syntax ");
END error;


PROCEDURE link(p,q: NodePtr);
VAR
  t: NodePtr;
BEGIN (* insert q in places indecated by linked chain p *)
  WHILE p#NIL DO
    t := p; p := t.suc; t.suc := q;
  END;
END link;


PROCEDURE expression(VAR p, q, r, s: NodePtr);
VAR
  q1, s1: NodePtr;

  PROCEDURE term(VAR p, q, r, s: NodePtr);
  VAR
    p1, q1, r1, s1: NodePtr;

    PROCEDURE factor(VAR p, q, r, s: NodePtr);
    VAR
      a: NodePtr;
      h: HeadPtr;
    BEGIN
      IF ("A" <= CAP(sym)) & (CAP(sym) <= "Z") THEN
        NEW(a);
        find(sym,h);
        a.terminal := FALSE;
        a.nsym := h;
        a.alt := NIL;
        a.suc := NIL;
        p := a; q := a; r := a; s := a;
        GetSym;
      ELSIF sym = '"' THEN (* terminal symbol *)
        GetSym;
        NEW(a);
        a.terminal := TRUE;
        a.tsym := sym;
        a.alt := NIL;
        a.suc := NIL;
        p := a; q := a; r := a; s := a;
        GetSym;
        IF sym = '"' THEN GetSym ELSE error; END;
      ELSIF sym = "(" THEN
        GetSym;
        expression(p,q,r,s);
        IF sym = ")" THEN GetSym ELSE error; END;
      ELSIF sym = "[" THEN
        GetSym;
        expression(p,q,r,s);
        NEW(a);
        a.terminal := TRUE;
        a.tsym := empty;
        a.alt := NIL;
        a.suc := NIL;
        q.alt := a; s.suc := a; q := a; s := a;
        IF sym = "]" THEN GetSym ELSE error; END;
      ELSIF sym = "{" THEN
        GetSym;
        expression(p,q,r,s);
        link(r,p);
        NEW(a);
        a.terminal := TRUE;
        a.tsym := empty;
        a.alt := NIL;
        a.suc := NIL;
        q.alt := a; r := a; q := a; s := a;
        IF sym = "}" THEN GetSym ELSE error; END;
      ELSE error;
      END;
    END factor;

  BEGIN (* term *)
    factor (p,q,r,s);
    WHILE ("A" <= CAP(sym)) & (CAP(sym) <= "Z") OR
          (sym = '"') OR (sym = "(") OR (sym = "[") OR
          (sym = "{") DO
      factor(p1,q1,r1,s1);
    END;
  END term;

BEGIN (* expression *)
  term (p,q,r,s);
  WHILE sym = "|" DO
    GetSym;
    term(q.alt,q1,s.suc,s1);
    q := q1; s := s1;
  END;
END expression;


PROCEDURE parse(goal: HeadPtr; VAR match: BOOLEAN);
VAR
  s: NodePtr;
BEGIN
  s := goal.entry;
  REPEAT
    IF s.terminal THEN
      IF s.tsym = sym THEN
        match := TRUE;
        GetSym;
      ELSE
        match := s.tsym = empty;
      END;
    ELSE
      parse(s.nsym,match);
    END;
    IF match THEN s := s.suc; ELSE s := s.alt; END;
  UNTIL s = NIL;
END parse;


BEGIN (* main *)
  IF fs.Open(file,"EBNF",FALSE) THEN noerr := TRUE;
    NEW(sentinel); list := sentinel;

    (* read products and buils data structure *)
    LOOP
      GetSym;
      IF sym = "$" THEN EXIT; END;
      find (sym,h);
      GetSym;
      IF sym = "=" THEN GetSym ELSE error END;
      expression(h.entry,q,r,s);
      link(r,NIL);
      IF sym # "." THEN error END;
    END;

    IF noerr THEN
      h := list;
      (* check wether all symbols are defined *)
      WHILE h # sentinel DO
        IF h.entry = NIL THEN
          io.WriteString(" undefined Symbol ");
          io.Write(h.sym); io.WriteLn;
          noerr := FALSE;
        END;
        h := h.suc;
      END;
    END;

    IF noerr THEN (* read goal symbol *)
      GetSym; find (sym,h); io.WriteLn;
      IF fs.Close(file) THEN END;
      (* read and parse sentences *)
      LOOP
        io.Write(">");
        GetSym;
        IF sym = asc.esc THEN EXIT END;
        parse(h,noerr);
        IF noerr & (sym = asc.esc) THEN
          io.WriteString("  correct\n");
        ELSE
          io.WriteString("  incorrect\n");
        END;
      END;
    ELSE
      IF fs.Close(file) THEN END;
    END;
    io.WriteLn;
  END;
END GeneralParser.